package com.yangzhe.algorithm.c038;

// 打印n层汉诺塔问题的最优移动轨迹
public class Code07_TowerOfHanoi {

    /**
     * 思路:递归、分治
     * 有三根柱子：A（源）、B（辅助）、C（目标）
     * 要将 n 个盘子从 A 移动到 C，借助 B：
     * <p>
     * 先将上面的 n-1 个盘子从 A 移动到 B（借助 C 作为辅助）
     * 再将第 n 个（最大的）盘子从 A 移动到 C
     * 最后将 n-1 个盘子从 B 移动到 C（借助 A 作为辅助）
     * 这个过程是递归的，直到 n = 1 时直接移动。
     * <p>
     * 总移动次数：2^n - 1，这是最优解。
     *
     * @param n
     */
    public static void hanoi(int n) {
        move("左", "右", "中", n);
    }

    public static void move(String from, String to, String aux, int n) {
        if (n == 0) {
            return;
        }

        move(from, aux, to, n - 1);
        System.out.println(n + "从" + from + "到" + to);
        move(aux, to, from, n - 1);
    }


    public static void main(String[] args) {
        int n = 1;
        hanoi(n);
    }

}
